{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count All Possible Routes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #memoization #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #记忆化搜索 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countRoutes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计所有可行路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <strong>互不相同</strong>&nbsp;的整数数组，其中&nbsp;<code>locations[i]</code>&nbsp;表示第&nbsp;<code>i</code>&nbsp;个城市的位置。同时给你&nbsp;<code>start</code>，<code>finish</code>&nbsp;和&nbsp;<code>fuel</code>&nbsp;分别表示出发城市、目的地城市和你初始拥有的汽油总量</p>\n",
    "\n",
    "<p>每一步中，如果你在城市 <code>i</code>&nbsp;，你可以选择任意一个城市 <code>j</code>&nbsp;，满足 &nbsp;<code>j != i</code>&nbsp;且&nbsp;<code>0 &lt;= j &lt; locations.length</code>&nbsp;，并移动到城市&nbsp;<code>j</code>&nbsp;。从城市&nbsp;<code>i</code>&nbsp;移动到&nbsp;<code>j</code>&nbsp;消耗的汽油量为&nbsp;<code>|locations[i] - locations[j]|</code>，<code>|x|</code>&nbsp;表示&nbsp;<code>x</code>&nbsp;的绝对值。</p>\n",
    "\n",
    "<p>请注意，&nbsp;<code>fuel</code>&nbsp;任何时刻都&nbsp;<strong>不能</strong>&nbsp;为负，且你&nbsp;<strong>可以</strong>&nbsp;经过任意城市超过一次（包括&nbsp;<code>start</code>&nbsp;和&nbsp;<code>finish</code>&nbsp;）。</p>\n",
    "\n",
    "<p>请你返回从<em>&nbsp;</em><code>start</code>&nbsp;到&nbsp;<code>finish</code>&nbsp;所有可能路径的数目。</p>\n",
    "\n",
    "<p>由于答案可能很大， 请将它对&nbsp;<code>10^9 + 7</code>&nbsp;取余后返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>以下为所有可能路径，每一条都用了 5 单位的汽油：\n",
    "1 -&gt; 3\n",
    "1 -&gt; 2 -&gt; 3\n",
    "1 -&gt; 4 -&gt; 3\n",
    "1 -&gt; 4 -&gt; 2 -&gt; 3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>locations = [4,3,1], start = 1, finish = 0, fuel = 6\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>以下为所有可能的路径：\n",
    "1 -&gt; 0，使用汽油量为 fuel = 1\n",
    "1 -&gt; 2 -&gt; 0，使用汽油量为 fuel = 5\n",
    "1 -&gt; 2 -&gt; 1 -&gt; 0，使用汽油量为 fuel = 5\n",
    "1 -&gt; 0 -&gt; 1 -&gt; 0，使用汽油量为 fuel = 3\n",
    "1 -&gt; 0 -&gt; 1 -&gt; 0 -&gt; 1 -&gt; 0，使用汽油量为 fuel = 5\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>locations = [5,2,1], start = 0, finish = 2, fuel = 3\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>没有办法只用 3 单位的汽油从 0 到达 2 。因为最短路径需要 4 单位的汽油。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= locations.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= locations[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li>所有&nbsp;<code>locations</code>&nbsp;中的整数 <strong>互不相同</strong>&nbsp;。</li>\n",
    "\t<li><code>0 &lt;= start, finish &lt;&nbsp;locations.length</code></li>\n",
    "\t<li><code>1 &lt;= fuel &lt;= 200</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-all-possible-routes](https://leetcode.cn/problems/count-all-possible-routes/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-all-possible-routes](https://leetcode.cn/problems/count-all-possible-routes/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,6,8,4]\\n1\\n3\\n5', '[4,3,1]\\n1\\n0\\n6', '[5,2,1]\\n0\\n2\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        n = len(locations)\n",
    "        mod = 1e9 + 7\n",
    "        dp = [[0 for _ in range(fuel + 1)] for _ in range(n)]\n",
    "        dp[start][fuel] = 1\n",
    "\n",
    "        for i in range(fuel, -1, -1):\n",
    "            for j in range(n):\n",
    "                for k in range(n):\n",
    "                    if j != k and dp[j][i] != 0:\n",
    "                        dis = abs(locations[j] - locations[k])\n",
    "                        if i - dis >= 0:\n",
    "                            dp[k][i - dis] += dp[j][i]\n",
    "                            dp[k][i - dis] %= mod\n",
    "\n",
    "        return int(sum(dp[finish]) % mod) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        n = len(locations)\n",
    "        dp = [[0]*n for _ in range(fuel+1)]\n",
    "        # dp[i][j]表示油量i，从起点start到第j个城市的所有路径数\n",
    "        # dp[0][start] = 1\n",
    "        # dp[i][start] (i>0) 一开始也有i=0时的一条路径，后面可以将继续更新\n",
    "        for i in range(fuel+1):\n",
    "            dp[i][start] = 1\n",
    "        for i in range(1,fuel+1):\n",
    "            for j in range(n):\n",
    "                for p in range(n):\n",
    "                    if p!=j:\n",
    "                        rest_fuel = i-abs(locations[p]-locations[j])\n",
    "                        if rest_fuel>=0:\n",
    "                            dp[i][j] = dp[i][j] + dp[rest_fuel][p]\n",
    "                            # 当前油量去p城市，再从p城市回来\n",
    "                dp[i][j]=dp[i][j]%MOD\n",
    "        return dp[fuel][finish]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(locations)\n",
    "        startPos = locations[start]\n",
    "        finishPos = locations[finish]\n",
    "        locations.sort()\n",
    "        start = locations.index(startPos)\n",
    "        finish = locations.index(finishPos)\n",
    "        dpL = [[0] * (fuel + 1) for _ in range(n)]\n",
    "        dpR = [[0] * (fuel + 1) for _ in range(n)]\n",
    "        dpL[start][0] = dpR[start][0] = 1\n",
    "        for used in range(fuel + 1):\n",
    "            for city in range(n - 2, -1, -1):\n",
    "                if (delta := locations[city + 1] - locations[city]) <= used:\n",
    "                    dpL[city][used] = ((0 if used == delta else dpL[city + 1][used - delta]) * 2 + dpR[city + 1][used - delta]) % mod\n",
    "            for city in range(1, n):\n",
    "                if (delta := locations[city] - locations[city - 1]) <= used:\n",
    "                    dpR[city][used] = ((0 if used == delta else dpR[city - 1][used - delta]) * 2 + dpL[city - 1][used - delta]) % mod\n",
    "        ans = sum(dpL[finish]) + sum(dpR[finish])\n",
    "        if start == finish:\n",
    "            ans -= 1\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        dp = [[0] * len(locations) for _ in range(fuel + 1)]\n",
    "        dp[fuel][start] = 1\n",
    "        use = 0\n",
    "        for i in range(fuel, 0, -1):\n",
    "            for x in range(len(locations)):\n",
    "                for y in range(len(locations)):\n",
    "                    if x==y:\n",
    "                        continue\n",
    "                    use = abs(locations[x] - locations[y])\n",
    "                    if i >= use:\n",
    "                        dp[i - use][y] += dp[i][x]\n",
    "        res = 0\n",
    "        for i in range(fuel+1):\n",
    "            res += dp[i][finish]\n",
    "            res%=10**9+7\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        \n",
    "        # 生成 hash 字典的内部函数\n",
    "        def generate_hash(num, start_index, end_index, fuel):\n",
    "            hash_dict = {}\n",
    "            start, end = min(start_index, end_index), max(start_index, end_index)\n",
    "            for i in range(len(num)):  # 修改为遍历整个 locations 数组\n",
    "                for j in range(len(num)):\n",
    "                    if i == j:\n",
    "                        continue\n",
    "                    if i not in hash_dict:\n",
    "                        hash_dict[i] = {}\n",
    "                    diff = abs(num[i] - num[j])\n",
    "                    hash_dict[i][j] = diff <= fuel\n",
    "                    if j not in hash_dict:\n",
    "                        hash_dict[j] = {}\n",
    "                    hash_dict[j][i] = hash_dict[i][j]\n",
    "            return hash_dict\n",
    "\n",
    "        # 生成 hash 字典\n",
    "        hash_dict = generate_hash(locations, min(start, finish), max(start, finish), fuel)\n",
    "        \n",
    "        # 初始化 DP 字典\n",
    "        dp = {}\n",
    "        dp[(start, fuel)] = 1\n",
    "        \n",
    "        # DP 过程\n",
    "        for f in range(fuel, -1, -1):\n",
    "            for i in range(len(locations)):  # 修改为遍历整个 locations 数组\n",
    "                if (i, f) not in dp:\n",
    "                    continue\n",
    "                for j in hash_dict[i]:\n",
    "                    if hash_dict[i][j]:\n",
    "                        cost = abs(locations[i] - locations[j])\n",
    "                        next_fuel = f - cost\n",
    "                        if next_fuel >= 0:\n",
    "                            dp[(j, next_fuel)] = dp.get((j, next_fuel), 0) + dp[(i, f)]\n",
    "                            dp[(j, next_fuel)] %= MOD\n",
    "\n",
    "        # 计算结果\n",
    "        result = sum(dp.get((finish, f), 0) for f in range(fuel + 1)) % MOD\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(locations)\n",
    "        cache = [[-1]*(fuel+1) for _ in range(n)]\n",
    "        \n",
    "\n",
    "        def dfs(locations: List[int], cur: int, target: int, fuel: int):\n",
    "            if cache[cur][fuel] != -1:\n",
    "                return cache[cur][fuel]\n",
    "\n",
    "            if fuel == 0 and cur != target:\n",
    "                cache[cur][fuel] = 0\n",
    "                return 0\n",
    "\n",
    "            hasNext = False\n",
    "            for i in range(n):\n",
    "                if i != cur:\n",
    "                    need = abs(locations[cur] - locations[i])\n",
    "                    if fuel >= need:\n",
    "                        hasNext = True\n",
    "                        break\n",
    "            \n",
    "            if fuel != 0 and not hasNext:\n",
    "                cache[cur][fuel] = 1 if cur == target else 0\n",
    "                return cache[cur][fuel]\n",
    "            \n",
    "            sum = 1 if cur == target else 0\n",
    "            for i in range(n):\n",
    "                if i != cur:\n",
    "                    need = abs(locations[i] - locations[cur])\n",
    "                    if fuel >= need:\n",
    "                        sum += dfs(locations, i, target, fuel - need)\n",
    "                        sum %= mod\n",
    "                    \n",
    "            cache[cur][fuel] = sum\n",
    "            return sum\n",
    "\n",
    "        return dfs(locations, start, finish, fuel)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        # # cache=[ [-1,] * (fuel+1) ,] * len(locations)   你的代码中，cache的初始化有问题。你使用了cache=[ [-1,] * (fuel+1) ,] * len(locations)，这样会导致所有的子列表都是同一个对象的引用，修改其中一个子列表，其他的子列表也会跟着改变。你应该使用列表推导式来创建二维列表\n",
    "        # cache = [[-1 for _ in range(fuel+1)] for _ in range(len(locations))]\n",
    "        # def dfs(loc, cur, fin, fuel):\n",
    "        #     # print(f'cur visited:{cur}, left fuel is {fuel}')\n",
    "        #     if fuel<0:\n",
    "        #         return 0\n",
    "\n",
    "        #     if cache[cur][fuel] != -1:\n",
    "        #         return cache[cur][fuel]\n",
    "            \n",
    "        #     has_next=False\n",
    "        #     for tar in range(len(loc)):\n",
    "        #         need=abs(loc[cur] - loc[tar])\n",
    "        #         if tar != cur and  fuel-need >= 0:\n",
    "        #             has_next=True \n",
    "        #             break\n",
    "\n",
    "        #     if fuel>=0 and not has_next:\n",
    "        #         cache[cur][fuel] = 1 if cur==fin else 0\n",
    "        #         return cache[cur][fuel]\n",
    "\n",
    "\n",
    "        #     _sum=0\n",
    "        #     if cur ==fin and fuel>=0:\n",
    "        #         _sum=1\n",
    "        #     for tar in range(len(loc)):\n",
    "        #         if tar != cur:\n",
    "        #             need=abs(loc[cur] - loc[tar])\n",
    "        #             _sum += dfs(loc, tar, fin, fuel-need)\n",
    "        #             _sum=_sum%1000000007\n",
    "        #     cache[cur][fuel] = _sum\n",
    "        #     return _sum\n",
    "        # res=dfs(locations,start,finish,fuel)\n",
    "        # return res\n",
    "\n",
    "        cache = [[-1 for _ in range(fuel+1)] for _ in range(len(locations))]\n",
    "        def dfs(loc, cur, fin, fuel):\n",
    "            if fuel<0:\n",
    "                return 0\n",
    "            if cache[cur][fuel] != -1:\n",
    "                return cache[cur][fuel]\n",
    "            _sum = 1 if cur == fin else 0\n",
    "            for tar in range(len(loc)):\n",
    "                if tar != cur:\n",
    "                    need = abs(loc[cur] - loc[tar])\n",
    "                    _sum += dfs(loc, tar, fin, fuel-need)\n",
    "                    _sum=_sum%1000000007\n",
    "            cache[cur][fuel] = _sum\n",
    "            return _sum\n",
    "        res = dfs(locations, start, finish, fuel)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        # cache=[ [-1,] * (fuel+1) ,] * len(locations)   你的代码中，cache的初始化有问题。你使用了cache=[ [-1,] * (fuel+1) ,] * len(locations)，这样会导致所有的子列表都是同一个对象的引用，修改其中一个子列表，其他的子列表也会跟着改变。你应该使用列表推导式来创建二维列表\n",
    "        cache = [[-1 for _ in range(fuel+1)] for _ in range(len(locations))]\n",
    "        def dfs(loc, cur, fin, fuel):\n",
    "            if fuel<0:\n",
    "                return 0\n",
    "\n",
    "            if cache[cur][fuel] != -1:\n",
    "                return cache[cur][fuel]\n",
    "\n",
    "            if abs(loc[cur] - loc[fin]) > fuel and cur!=fin:\n",
    "                cache[cur][fuel]=0\n",
    "                return 0\n",
    "\n",
    "            _sum=0\n",
    "            if cur ==fin:\n",
    "                _sum=1\n",
    "            for tar in range(len(loc)):\n",
    "                if tar != cur:\n",
    "                    need=abs(loc[cur] - loc[tar])\n",
    "                    _sum += dfs(loc, tar, fin, fuel-need)\n",
    "                    _sum=_sum%1000000007\n",
    "            cache[cur][fuel] = _sum\n",
    "            return _sum\n",
    "        res=dfs(locations,start,finish,fuel)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        def dfs(pos, remain):\n",
    "            if dp[pos][remain] != -1:\n",
    "                return dp[pos][remain]\n",
    "\n",
    "            if remain < abs(locations[pos] - locations[finish]):\n",
    "                dp[pos][remain] = 0\n",
    "                return 0\n",
    "            \n",
    "            sum = 1 if pos == finish else 0\n",
    "            for i in range(n):\n",
    "                if i != pos:\n",
    "                    need = abs(locations[pos] - locations[i])\n",
    "                    if need <= remain:\n",
    "                        sum += dfs(i, remain - need)\n",
    "                        sum %= mod\n",
    "            \n",
    "            dp[pos][remain] = sum\n",
    "            return sum\n",
    "\n",
    "        mod = 1000000007\n",
    "        n = len(locations)\n",
    "        \n",
    "        dp = [[-1] * (fuel + 1) for _ in range(n)]\n",
    "        return dfs(start, fuel)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        mod = 1e9+7\n",
    "        n = len(locations)\n",
    "        cache = [[-1 for i in range(fuel+1)] for i in range(n)]\n",
    "\n",
    "        def dfs(locations,cur,finish,fuel):\n",
    "            if cache[cur][fuel]!=-1:\n",
    "                return cache[cur][fuel]\n",
    "            n = len(locations)\n",
    "            if fuel==0 and cur!=finish:\n",
    "                cache[cur][fuel] = 0\n",
    "                return 0 \n",
    "            \n",
    "            hasNext = False\n",
    "            for i in range(n):\n",
    "                if i!=cur:\n",
    "                    need = abs(locations[cur]-locations[i])\n",
    "                    if fuel>=need:\n",
    "                        hasNext = True\n",
    "                        break\n",
    "            if fuel!=0 and hasNext==False:\n",
    "                a = cache[cur][fuel] = 1 if cur==finish else 0\n",
    "                return a \n",
    "\n",
    "            res = 1 if cur==finish else 0 \n",
    "            for i in range(n):\n",
    "                if i!=cur:\n",
    "                    need = abs(locations[i]-locations[cur])\n",
    "                    if fuel>=need:\n",
    "                        res+=dfs(locations,i,finish,fuel-need)\n",
    "                        res%=mod \n",
    "            cache[cur][fuel] = res\n",
    "            return res \n",
    "\n",
    "        return int(dfs(locations,start,finish,fuel))\n",
    "\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        q = [(0, start)]\n",
    "        c = defaultdict(int)\n",
    "        c[(0, start)] = 1\n",
    "        n = len(locations)\n",
    "        visited = set(q)\n",
    "        while q:\n",
    "            used, idx = heapq.heappop(q)\n",
    "            # print(q)\n",
    "            if used > fuel:\n",
    "                break\n",
    "            for i in range(n):\n",
    "                if i != idx:\n",
    "                    new_used = used + abs(locations[idx] - locations[i])\n",
    "                    c[(new_used, i)] += c[(used, idx)]\n",
    "                    if (new_used,i) not in visited:\n",
    "                        visited.add((new_used,i))\n",
    "                        heapq.heappush(q, (new_used,i))\n",
    "        return sum(c[(i, finish)] for i in range(0, fuel + 1)) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        mod=10**9+7\n",
    "        n=len(locations)\n",
    "        dp=[[-1]*(fuel+1) for _ in range(n)]\n",
    "        cost=[[abs(locations[i]-locations[j]) for i in range(n)] for j in range(n)]\n",
    "\n",
    "        def dfs(s,e,f):\n",
    "            if dp[s][f]!=-1:\n",
    "                return dp[s][f]\n",
    "            \n",
    "            if cost[s][e]>f:\n",
    "                dp[s][f]=0\n",
    "                return 0\n",
    "            \n",
    "            if s==e:\n",
    "                sum=1\n",
    "            else:\n",
    "                sum=0\n",
    "            for i in range(n):\n",
    "                if i!=s:\n",
    "                    if f>=cost[s][i]:\n",
    "                        sum+=dfs(i,e,f-cost[s][i])\n",
    "                        sum%=mod\n",
    "            dp[s][f]=sum\n",
    "            return sum\n",
    "        \n",
    "        return dfs(start,finish,fuel)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        @cache\n",
    "        def dfs(cur,fuel):\n",
    "            ans = int(cur == finish)\n",
    "            for i,j in enumerate(locations):\n",
    "                csm =  abs(j-locations[cur])\n",
    "                if i!=cur and fuel >= csm:\n",
    "                    ans += dfs(i,fuel - csm)\n",
    "            return ans%(10**9+7)\n",
    "        return dfs(start,fuel)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, loc: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i,x):\n",
    "            if abs(loc[i]-finish)>x: return 0\n",
    "            tot=0\n",
    "            # if loc[i]==finish:\n",
    "                # tot+=1\n",
    "                # return 1\n",
    "            if x>=0 and loc[i]==finish: tot+=1\n",
    "            # tot=0\n",
    "            # if abs(loc[i]-finish)<=x: \n",
    "            #     tot+=1\n",
    "            j=i+1\n",
    "            while j<n and abs(loc[j]-loc[i])+abs(loc[j]-finish)<=x:\n",
    "                tot+=dfs(j,x-abs(loc[j]-loc[i]))\n",
    "                j+=1\n",
    "            k=i-1\n",
    "            while k>=0 and abs(loc[k]-loc[i])+abs(loc[k]-finish)<=x:\n",
    "                tot+=dfs(k,x-abs(loc[k]-loc[i]))\n",
    "                k-=1\n",
    "            # if tot==0 and abs(loc[i]-finish)<=x: tot+=1\n",
    "            # print(i,loc[i],x,tot)\n",
    "            return tot%MOD\n",
    "        \n",
    "        MOD=10**9+7\n",
    "        \n",
    "        # if start not in locations: locations.append(start)\n",
    "        # if start not in locations: locations.append(start)\n",
    "\n",
    "        # print(locations)\n",
    "        start=loc[start]\n",
    "        finish=loc[finish]\n",
    "        loc.sort()\n",
    "        # loc=sorted(locations)\n",
    "        n=len(loc)\n",
    "        # loc=[]\n",
    "        s=bisect_left(loc,start)\n",
    "        t=bisect_left(loc,start)\n",
    "        # print(loc,s,start,t,finish)\n",
    "        return dfs(s,fuel)\n",
    "        # print(loc,r)\n",
    "        return dfs(r,fuel)\n",
    "        # ans=0\n",
    "        # for i,x in enumerate(loc):\n",
    "        #     if abs(x-start)+abs(x-finish)<=fuel:\n",
    "        #         ans+=dfs(i,fuel-abs(x-start))\n",
    "        # return ans%MOD\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        q = [(0, start)]\n",
    "        c = defaultdict(int)\n",
    "        c[(0, start)] = 1\n",
    "        n = len(locations)\n",
    "        visited = set(q)\n",
    "        while q:\n",
    "            used, idx = heapq.heappop(q)\n",
    "            # print(q)\n",
    "            if used > fuel:\n",
    "                break\n",
    "            for i in range(n):\n",
    "                if i != idx:\n",
    "                    new_used = used + abs(locations[idx] - locations[i])\n",
    "                    c[(new_used, i)] += c[(used, idx)]\n",
    "                    if (new_used,i) not in visited:\n",
    "                        visited.add((new_used,i))\n",
    "                        heapq.heappush(q, (new_used,i))\n",
    "        return sum(c[(i, finish)] for i in range(0, fuel + 1)) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        @lru_cache(maxsize=None)\n",
    "        def dfs(pos, rest):\n",
    "            if abs(locations[pos] - locations[finish]) > rest:\n",
    "                return 0\n",
    "                \n",
    "            ans = 0;\n",
    "            if rest!=0:\n",
    "                for i, loc in enumerate(locations):\n",
    "                    if pos != i:\n",
    "                        cost = abs(locations[pos] - loc)\n",
    "                        if cost <= rest:\n",
    "                            ans += dfs(i, rest - cost)\n",
    "            if pos == finish:\n",
    "                ans += 1\n",
    "            return ans % 1000000007\n",
    "                        \n",
    "        return dfs(start, fuel)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def dfs(node,fuel):\n",
    "            res = 0\n",
    "            if node == finish:\n",
    "                res +=1\n",
    "            for idx,i in enumerate(locations):\n",
    "                if idx == node:\n",
    "                    continue\n",
    "                temp = abs(locations[node]-i)\n",
    "                if fuel >= temp:\n",
    "                    res +=dfs(idx,fuel-temp)\n",
    "            return res % (10**9 +7)\n",
    "        \n",
    "        return dfs(start,fuel)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(pos, rest):\n",
    "            if abs(locations[pos] - locations[finish]) > rest:\n",
    "                return 0\n",
    "\n",
    "            ans = 0\n",
    "            for i, loc in enumerate(locations):\n",
    "                if i != pos:\n",
    "                    cost = abs(locations[pos] - loc)\n",
    "                    if cost <= rest:\n",
    "                        ans += dfs(i, rest - cost)\n",
    "            \n",
    "            if pos == finish:\n",
    "                ans += 1\n",
    "            return ans % 1000000007\n",
    "        \n",
    "        return dfs(start, fuel)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        n = len(locations)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(pos, rest):\n",
    "            if abs(locations[pos] - locations[finish]) > rest:\n",
    "                return 0\n",
    "                \n",
    "            ans = 0\n",
    "            for i, loc in enumerate(locations):\n",
    "                if pos != i:\n",
    "                    cost = abs(locations[pos] - loc)\n",
    "                    if cost <= rest:\n",
    "                        ans += dfs(i, rest - cost)\n",
    "            if pos == finish:\n",
    "                ans += 1\n",
    "            return ans % 1000000007\n",
    "                        \n",
    "        return dfs(start, fuel)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        N = len(locations)\n",
    "        cache = defaultdict()\n",
    "        # @lru_cache(None)\n",
    "        def travel(pos,gas):\n",
    "            if (pos,gas) in cache:\n",
    "                return cache[(pos,gas)]\n",
    "            if abs(locations[pos]-locations[finish])>gas:\n",
    "                return 0\n",
    "            count = 0\n",
    "            if pos == finish:\n",
    "                count += 1\n",
    "            for i in range(N):\n",
    "                if i!=pos:\n",
    "                    cost = abs(locations[pos] - locations[i])\n",
    "                    if cost<=gas:\n",
    "                        count +=travel(i,gas-cost)\n",
    "            cache[(pos,gas)]=count%(10**9+7)\n",
    "            return count%(10**9+7)\n",
    "        return travel(start,fuel)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        n = len(locations)\n",
    "        dist = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                dist[i][j] = abs(locations[i] - locations[j])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(start, fuel):\n",
    "            n = len(locations)\n",
    "            if start!= finish:\n",
    "                if fuel == 0 or sum([fuel >= i for i in (dist[start][:start] + dist[start][start + 1:])]) == 0: return 0\n",
    "\n",
    "            res = 1 if start == finish else 0\n",
    "            for i in range(n):\n",
    "                if i != start and fuel >= dist[start][i]:\n",
    "                    res = (res + dfs(i, fuel - dist[start][i])) % (10 ** 9 + 7)\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        return dfs(start, fuel)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        N = len(locations)\n",
    "        @lru_cache(None)\n",
    "        def travel(pos,gas):\n",
    "            if abs(locations[pos]-locations[finish])>gas:\n",
    "                return 0\n",
    "            count = 0\n",
    "            if pos == finish:\n",
    "                count += 1\n",
    "            \n",
    "            for i in range(N):\n",
    "                if i!=pos:\n",
    "                    cost = abs(locations[pos] - locations[i])\n",
    "                    if cost<=gas:\n",
    "                        count +=travel(i,gas-cost)\n",
    "            return count%(10**9+7)\n",
    "        return travel(start,fuel)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        if abs(locations[finish] -locations[start]) >fuel:\n",
    "            return 0\n",
    "        \n",
    "        cache ={}\n",
    "        f_loc =locations[finish]\n",
    "        \n",
    "        def dp_helper(loc,fuel_left):\n",
    "            \n",
    "            if fuel_left<0:\n",
    "                return 0\n",
    "            if abs(loc -f_loc) > fuel_left:\n",
    "                return 0\n",
    "            if (loc,fuel_left) in cache:\n",
    "                return cache[(loc,fuel_left)]\n",
    "            \n",
    "            base =0\n",
    "            if loc == f_loc:\n",
    "                base =1\n",
    "            \n",
    "                \n",
    "            for l in locations:\n",
    "                if l!=loc:\n",
    "                    base += dp_helper(l, fuel_left-abs(loc-l))\n",
    "            \n",
    "            cache[(loc,fuel_left)] =base\n",
    "            return base\n",
    "        \n",
    "        return dp_helper(locations[start], fuel)%(10**9+7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        n = len(locations)\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        # 预处理: 计算两两城市间的距离, 否则的话, 一对城市间的距离会重复计算多遍\n",
    "        D = [[0] * n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                D[i][j] = D[j][i] = abs(locations[i] - locations[j])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, fuel):\n",
    "            if i == finish:\n",
    "                ans = 1\n",
    "            else:\n",
    "                ans = 0\n",
    "\n",
    "            if fuel == 0:\n",
    "                return ans\n",
    "\n",
    "            # 剪枝: 如果目前的位置已经无法达到终点了, 提早终止\n",
    "            if D[i][finish] > fuel:\n",
    "                return ans\n",
    "                \n",
    "            for j in range(n):\n",
    "                if j == i: continue\n",
    "                dist = D[i][j]\n",
    "                if fuel >= dist:\n",
    "                    ans += dfs(j, fuel - dist)\n",
    "            return ans % MOD\n",
    "\n",
    "        return dfs(start, fuel)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        @functools.cache\n",
    "        def backtracking(start: int, fuel: int) -> int:\n",
    "            res = 0\n",
    "            if start == finish:\n",
    "                res += 1\n",
    "            # 剪枝\n",
    "            if fuel < abs(locations[start] - locations[finish]):\n",
    "                return 0\n",
    "            # 下一个城市去哪？\n",
    "            for i in range(len(locations)):\n",
    "                if i != start and fuel >= abs(locations[i] - locations[start]):\n",
    "                    res += backtracking(i, fuel - abs(locations[i] - locations[start]))\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        return backtracking(start, fuel) % (10 ** 9 + 7)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(idx, cost):\n",
    "            ans = 0\n",
    "            if cost > fuel or (fuel - cost) < abs(locations[idx] - locations[finish]): return ans\n",
    "            if idx == finish:\n",
    "                ans += 1\n",
    "            for i in range(len(locations)):\n",
    "                if idx != i:\n",
    "                    ans = (ans + dfs(i, cost + abs(locations[i] - locations[idx]))) % mod\n",
    "            return ans\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        return dfs(start, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        N = len(locations)\n",
    "        @lru_cache(None)\n",
    "        def travel(pos,gas):\n",
    "            if abs(locations[pos]-locations[finish])>gas:\n",
    "                return 0\n",
    "            count = 0\n",
    "            if pos == finish:\n",
    "                count += 1\n",
    "            \n",
    "            for i in range(N):\n",
    "                if i!=pos:\n",
    "                    count +=travel(i,gas-abs(locations[pos]-locations[i]))\n",
    "            return count%(10**9+7)\n",
    "        return travel(start,fuel)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        n = len(locations)\n",
    "        MOD = 10**9 + 7\n",
    "        def dis(x, y):\n",
    "            return abs(locations[x] - locations[y])\n",
    "        \n",
    "        @cache\n",
    "        def dfs(cur, remain) -> int:\n",
    "            if remain < dis(cur, finish):\n",
    "                return 0\n",
    "\n",
    "            res = 1 if cur == finish else 0\n",
    "\n",
    "            for nxt in range(n):\n",
    "                if nxt == cur:\n",
    "                    continue\n",
    "                r = dfs(nxt, remain - dis(nxt, cur))\n",
    "                res = (res + r) % MOD\n",
    "            return res\n",
    "        return dfs(start, fuel)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        MOD = int(1e9 + 7) \n",
    "        \n",
    "        @cache\n",
    "        def dfs(index,fuel):\n",
    "            need = abs(locations[finish] - locations[index])\n",
    "            if need > fuel:\n",
    "                return 0\n",
    "            ans = 1 if index == finish else 0\n",
    "            for i in range(len(locations)):\n",
    "                if i != index:\n",
    "                    ans += dfs(i,fuel-abs(locations[i] - locations[index])) % MOD \n",
    "            return ans\n",
    "        return dfs(start,fuel) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        n=len(locations)\n",
    "        mod=10**9+7\n",
    "        @cache\n",
    "        def dfs(start,fuel):\n",
    "            if fuel==0:\n",
    "                return 1 if start==finish else 0\n",
    "            if fuel<0:\n",
    "                return 0\n",
    "            ans=0\n",
    "            if abs(locations[start]-locations[finish])>fuel:\n",
    "                return 0\n",
    "            if start==finish:\n",
    "                ans+=1\n",
    "            for j in range(n):\n",
    "                if j==start:\n",
    "                    continue\n",
    "                x=abs(locations[start]-locations[j])\n",
    "                ans+=dfs(j,fuel-x)\n",
    "            return ans\n",
    "        return dfs(start,fuel)%mod\n",
    "                            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i: int, k: int) -> int:\n",
    "            if k < 0 or abs(locations[i] - locations[finish] > k):\n",
    "                return 0\n",
    "            ans = int(i == finish)\n",
    "            ans += sum(dfs(j, k - abs(locations[i] - x))\n",
    "                       for j, x in enumerate(locations) if j != i)\n",
    "            return ans % mod\n",
    "\n",
    "        mod = 10**9 + 7\n",
    "        return dfs(start, fuel)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "\n",
    "        @lru_cache(maxsize=10000)\n",
    "        def _dfs(cur, fuel):\n",
    "            ans = 0\n",
    "            if fuel < 0:\n",
    "                return None\n",
    "            elif cur == locations[finish]:\n",
    "                ans += 1\n",
    "                for last in locations:\n",
    "                    if cur == last:\n",
    "                        continue\n",
    "                    if fuel >= abs(cur - last):\n",
    "                        ans += _dfs(last, fuel - abs(cur - last))\n",
    "            else:\n",
    "                for last in locations:\n",
    "                    if cur == last:\n",
    "                        continue\n",
    "                    if fuel >= abs(cur - last):\n",
    "                        ans += _dfs(last, fuel - abs(cur - last))\n",
    "            return ans\n",
    "        return _dfs(locations[start], fuel) % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(x, f):\n",
    "            res = 0\n",
    "            if x == finish:\n",
    "                res += 1\n",
    "            for s, y in dis[x]:\n",
    "                if s <= f:\n",
    "                    res += dfs(y, f - s)\n",
    "                else:\n",
    "                    break\n",
    "            return res % MOD\n",
    "\n",
    "        n = len(locations)\n",
    "        dis = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            for j in range(i + 1, n):\n",
    "                dis[i].append([abs(locations[i] - locations[j]), j])\n",
    "                dis[j].append([abs(locations[i] - locations[j]), i])\n",
    "        for i in range(n):\n",
    "            dis[i].sort()\n",
    "        return dfs(start, fuel)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "    1. dfs(pos, rest)表示剩余油为rest，以pos点为起点到finish位置所有可能路径数；\n",
    "    2. 递归条件：rest -= cost[pos][next_pos]，其他非pos位置所有可行路径和；\n",
    "    3. 当cost[pos][finish] > rest， 从pos无法到达finish，此时递归停止，返回0，当cost[pos][finish] > rest时，还可以从pos继续到下一位置进行，需要注意pos = finish时，此时也算一次可行路径；\n",
    "'''\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "\n",
    "        def resume_matrix(locations):\n",
    "\n",
    "            matrix = [[0 for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if i != j:\n",
    "                        matrix[i][j] = matrix[j][i] = abs(locations[i] - locations[j])\n",
    "            return matrix\n",
    "\n",
    "        @lru_cache(None)\n",
    "        # 在位置 pos 出发，油量为 rest 的前提下，到达 end 的「路径数量」\n",
    "        # 注意的是，从 i->j 的油耗一定 <= i->k->j，因此当cost[pos][finish] > rest时需要直接返回0\n",
    "        def dfs(pos, rest):\n",
    "\n",
    "            if cost[pos][finish] > rest:\n",
    "                return 0\n",
    "            ans = 1 if pos == finish else 0\n",
    "\n",
    "            for next_pos in range(n):\n",
    "                if next_pos != pos:\n",
    "                    ans += dfs(next_pos, rest - cost[pos][next_pos])\n",
    "\n",
    "            return ans\n",
    "\n",
    "        n = len(locations)\n",
    "        cost = resume_matrix(locations)\n",
    "\n",
    "        return dfs(start, fuel) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "\n",
    "        def resume_matrix(locations):\n",
    "\n",
    "            matrix = [[0 for _ in range(n)] for _ in range(n)]\n",
    "\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if i != j:\n",
    "                        matrix[i][j] = matrix[j][i] = abs(locations[i] - locations[j])\n",
    "            return matrix\n",
    "\n",
    "        @lru_cache(None)\n",
    "        # 在位置 pos 出发，油量为 rest 的前提下，到达 end 的「路径数量」\n",
    "        def dfs(pos, rest):\n",
    "\n",
    "            if cost[pos][finish] > rest:\n",
    "                return 0\n",
    "            ans = 1 if pos == finish else 0\n",
    "\n",
    "            for next_pos in range(n):\n",
    "                if next_pos != pos:\n",
    "                    ans += dfs(next_pos, rest - cost[pos][next_pos])\n",
    "\n",
    "            return ans\n",
    "\n",
    "        n = len(locations)\n",
    "        cost = resume_matrix(locations)\n",
    "\n",
    "        return dfs(start, fuel) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        dist = abs(locations[start] - locations[finish])\n",
    "        if dist > fuel:\n",
    "            return 0\n",
    "\n",
    "        n = len(locations)\n",
    "\n",
    "        locindex = [(v, i) for i, v in enumerate(locations)]\n",
    "        locindex.sort()\n",
    "\n",
    "        locloc = {v[0]: i for i, v in enumerate(locindex)}\n",
    "\n",
    "        dp = [[0 for _ in range(fuel + 1)] for _ in range(n)]\n",
    "        dp[start][fuel] = 1\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        from functools import lru_cache\n",
    "\n",
    "        @lru_cache(maxsize=None)\n",
    "        def dfs(curLocIndex, restFuel):\n",
    "            # print(curLocIndex, restFuel)\n",
    "            if curLocIndex == start and restFuel == fuel:\n",
    "                return 1\n",
    "\n",
    "            if restFuel > fuel:\n",
    "                return 0\n",
    "\n",
    "            ans = 0\n",
    "            loc = locations[curLocIndex]\n",
    "            loci = locloc[loc]\n",
    "            for i in range(loci + 1, n):\n",
    "                destloc, destindex = locindex[i]\n",
    "                d = abs(destloc - loc)\n",
    "                if d + restFuel > fuel:\n",
    "                    break\n",
    "                ans += dfs(destindex, restFuel + d)\n",
    "                ans %= mod\n",
    "            for i in range(loci-1, -1, -1):\n",
    "                destloc, destindex = locindex[i]\n",
    "                d = abs(destloc - loc)\n",
    "                if d + restFuel > fuel:\n",
    "                    break\n",
    "                ans += dfs(destindex, restFuel + d)\n",
    "                ans %= mod\n",
    "\n",
    "            return ans\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(fuel + 1):\n",
    "            ans += dfs(finish, i)\n",
    "            ans %= mod\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def countRoutes(self, locations, start: int, finish: int, fuel: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        N = len(locations)\n",
    "        # dp[end][f] = start到end点正好花费f的油的路径数\n",
    "        @lru_cache(None)\n",
    "        def helper(end,f):\n",
    "            if f == 0:\n",
    "                if end==start:return 1\n",
    "                else:return 0\n",
    "            dp = 0\n",
    "            for i in range(N):\n",
    "                if i==end:continue\n",
    "                dd = abs(locations[i]-locations[end])\n",
    "                if f >= dd:\n",
    "                    dp += helper(i,f-dd)%mod\n",
    "            return dp\n",
    "        res = 0\n",
    "        for f in range(fuel+1):\n",
    "            res += helper(finish,f)%mod\n",
    "        return res%mod\n",
    "        # dp = [[0]*(fuel+1) for _ in range(N)]\n",
    "        # dp[start][0] = 1\n",
    "        # for f in range(fuel+1):\n",
    "        #     for i in range(N):\n",
    "        #         for j in range(N):\n",
    "        #             if i==j:continue\n",
    "        #             dd = abs(locations[i]-locations[j])\n",
    "        #             if f>=dd:\n",
    "        #                 dp[j][f] += dp[i][f-dd]\n",
    "        # res = 0\n",
    "        # for f in range(fuel+1):\n",
    "        #     res += dp[finish][f]\n",
    "        # return res % (10**9+7)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "# import sys\n",
    "# sys.setrecursionlimit(1000000000)\n",
    "class Solution:\n",
    "    def countRoutes(self, locations, start: int, finish: int, fuel: int) -> int:\n",
    "        N = len(locations)\n",
    "        # dp[end][f] = start到end点正好花费f的油的路径数\n",
    "        @lru_cache(None)\n",
    "        def helper(end,f):\n",
    "            if f == 0:\n",
    "                if end==start:return 1\n",
    "                else:return 0\n",
    "            res = 0\n",
    "            for i in range(N):\n",
    "                if i==end:continue\n",
    "                dd = abs(locations[i]-locations[end])\n",
    "                if f >= dd:\n",
    "                    res += helper(i,f-dd)\n",
    "            return res\n",
    "        res = 0\n",
    "        for f in range(fuel+1):\n",
    "            res += helper(finish,f)\n",
    "        return res%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def countRoutes(self, locations, start: int, finish: int, fuel: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        N = len(locations)\n",
    "        # dp[end][f] = start到end点正好花费f的油的路径数\n",
    "        @lru_cache(None)\n",
    "        def helper(end,f):\n",
    "            if f == 0:\n",
    "                if end==start:return 1\n",
    "                else:return 0\n",
    "            dp = 0\n",
    "            for i in range(N):\n",
    "                if i==end:continue\n",
    "                dd = abs(locations[i]-locations[end])\n",
    "                if f >= dd:\n",
    "                    dp += helper(i,f-dd)\n",
    "            return dp\n",
    "        res = 0\n",
    "        for f in range(fuel+1):\n",
    "            res += helper(finish,f)\n",
    "        return res%mod\n",
    "        # dp = [[0]*(fuel+1) for _ in range(N)]\n",
    "        # dp[start][0] = 1\n",
    "        # for f in range(fuel+1):\n",
    "        #     for i in range(N):\n",
    "        #         for j in range(N):\n",
    "        #             if i==j:continue\n",
    "        #             dd = abs(locations[i]-locations[j])\n",
    "        #             if f>=dd:\n",
    "        #                 dp[j][f] += dp[i][f-dd]\n",
    "        # res = 0\n",
    "        # for f in range(fuel+1):\n",
    "        #     res += dp[finish][f]\n",
    "        # return res % (10**9+7)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        n = len(locations)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(p: int, f: int) -> int:\n",
    "            if f == 0:\n",
    "                return 0 + (p == start)\n",
    "            acc = 0\n",
    "            for i in range(n):\n",
    "                if p != i and f >= abs(locations[i]-locations[p]):\n",
    "                    acc += dfs(i, f-abs(locations[i]-locations[p]))\n",
    "            return acc % MOD\n",
    "        return sum([dfs(finish, f) for f in range(0, fuel+1)]) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        N = len(locations)\n",
    "        adj = [[] for _ in range(N)]\n",
    "        for i in range(N):\n",
    "            for j in range(N):\n",
    "                if i != j:\n",
    "                    adj[i].append((abs(locations[i] - locations[j]), j))\n",
    "        for i in range(N):\n",
    "            adj[i].sort()\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(cur, fuel):\n",
    "            res = 0\n",
    "            if cur == finish:\n",
    "                res += 1\n",
    "            for f, nei in adj[cur]:\n",
    "                if f > fuel:\n",
    "                    break\n",
    "                res += dfs(nei, fuel - f)\n",
    "            return res\n",
    "        res = dfs(start, fuel)\n",
    "        return res % (10 ** 9 + 7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp = [[0 for i in range(fuel + 1)] for i in range(len(locations))]\n",
    "\n",
    "        dp[finish][0] = 1\n",
    "\n",
    "        queue = [(0, finish)]\n",
    "\n",
    "        visited = set()\n",
    "\n",
    "        dist = [[0 for i in range(len(locations))] for i in range(len(locations))]\n",
    "\n",
    "        for i in range(len(locations)):\n",
    "            for j in range(i):\n",
    "                dist[j][i] = abs(locations[i] - locations[j])\n",
    "                dist[i][j] = abs(locations[j] - locations[i])\n",
    "\n",
    "        while queue:\n",
    "            f, loc = heapq.heappop(queue)\n",
    "            if (f, loc) in visited:\n",
    "                continue\n",
    "            visited.add((f, loc))\n",
    "            for i in range(len(locations)):\n",
    "                if i != loc:\n",
    "                    newF = f + dist[i][loc]\n",
    "                    if newF <= fuel:\n",
    "                        dp[i][newF] += dp[loc][f] % mod\n",
    "                        heapq.heappush(queue, (newF, i))\n",
    "        \n",
    "        return sum(dp[start][:]) % mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @functools.lru_cache(None)\n",
    "    def help(self, locations, start, finish, fuel):\n",
    "        ret = 0\n",
    "        if start == finish:\n",
    "            ret += 1\n",
    "        for i in range(len(locations)):\n",
    "            if i != start:\n",
    "                temp = fuel - abs(locations[i] - locations[start])\n",
    "                if temp < 0:\n",
    "                    continue\n",
    "                ret += self.help(locations, i, finish, temp)\n",
    "        return ret\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        locations = tuple(locations)     \n",
    "        return self.help(locations, start, finish, fuel) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i: int, k: int):\n",
    "            if k < 0 or abs(locations[i] - locations[finish] > k):\n",
    "                return 0\n",
    "            ans = int(i == finish)\n",
    "            for j, x in enumerate(locations):\n",
    "                if j != i:\n",
    "                    ans = (ans + dfs(j, k - abs(locations[i] - x))) % mod\n",
    "            return ans\n",
    "\n",
    "        mod = 10**9 + 7\n",
    "        return dfs(start, fuel)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "def printf(func):\n",
    "    def wrapper(*args):\n",
    "        ret = func(*args)\n",
    "        print (args, ret)\n",
    "        return ret\n",
    "    return wrapper\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        n = len(locations)\n",
    "        dis = [sorted([(abs(locations[i]-locations[j]), j)\n",
    "                       for j in range(n) if i != j]) for i in range(n)]\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def f(start: int, fuel: int) -> int:\n",
    "            ret = int(start == finish)\n",
    "            t = bisect.bisect_right(dis[start], (fuel, 999))\n",
    "            for i in range(t):\n",
    "                ret += f(dis[start][i][1], fuel - dis[start][i][0])\n",
    "\n",
    "            return ret % 1000000007\n",
    "        return f(start, fuel)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        self.locations = locations\n",
    "        self.max_value = 10**9 + 7\n",
    "        self.finish = finish\n",
    "        return self.dfs(start, fuel)\n",
    "        \n",
    "\n",
    "    @cache\n",
    "    def dfs(self, start: int, fuel: int) -> int:\n",
    "        cnt = 1 if start == self.finish else 0\n",
    "        li = self.locations[start]\n",
    "        for i, lval in enumerate(self.locations):\n",
    "            if i!=start:\n",
    "                ifuel = fuel-abs(li-lval)\n",
    "                if ifuel>=0:\n",
    "                    cnt = cnt + self.dfs(i, ifuel)\n",
    "                    if cnt>self.max_value: cnt -= self.max_value\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        self.locations = locations\n",
    "        self.max_value = 10**9 + 7\n",
    "        self.finish = finish\n",
    "        self.lfinish = locations[finish]\n",
    "        return self.dfs(start, fuel)\n",
    "        \n",
    "\n",
    "    @cache\n",
    "    def dfs(self, start: int, fuel: int) -> int:\n",
    "        cnt = 0\n",
    "        li = self.locations[start]\n",
    "        if start == self.finish: cnt = 1\n",
    "        elif abs(li-self.lfinish)>fuel: return 0\n",
    "\n",
    "        for i, lval in enumerate(self.locations):\n",
    "            if i!=start:\n",
    "                ifuel = fuel-abs(li-lval)\n",
    "                if ifuel>=0:\n",
    "                    cnt = cnt + self.dfs(i, ifuel)\n",
    "                    if cnt>self.max_value: cnt -= self.max_value\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        self.locations = locations\n",
    "        self.max_value = 10**9 + 7\n",
    "        self.finish = finish\n",
    "        self.lfinish = locations[finish]\n",
    "        return self.dfs(start, fuel)\n",
    "        \n",
    "\n",
    "    @cache\n",
    "    def dfs(self, start: int, fuel: int) -> int:\n",
    "        cnt = 0\n",
    "        li = self.locations[start]\n",
    "        if start == self.finish: cnt = 1\n",
    "        elif abs(li-self.lfinish)>fuel: return 0\n",
    "\n",
    "        for i, lval in enumerate(self.locations):\n",
    "            if i!=start:\n",
    "                ifuel = fuel-abs(li-lval)\n",
    "                if ifuel>=0:\n",
    "                    cnt = cnt + self.dfs(i, ifuel)\n",
    "                    if cnt>self.max_value: cnt -= self.max_value\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    mod = 10**9+7\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        adj = [[] for _ in range(len(locations))]\n",
    "        for i in range(len(locations)):\n",
    "            for j in range(i+1, len(locations)):\n",
    "                w = abs(locations[i]-locations[j])\n",
    "                adj[i].append((j, w))\n",
    "                adj[j].append((i, w))\n",
    "        mem = {}\n",
    "        def dfs(g, i, r):\n",
    "            if r == 0:\n",
    "                return 1 if i == g else 0\n",
    "            if mem.get((i, r), None) is not None:\n",
    "                return mem[(i, r)]                \n",
    "            cur = 1 if i == g else 0\n",
    "            for j, w in adj[i]:\n",
    "                if w <= r:\n",
    "                    cur = (cur+dfs(g, j, r-w))%self.mod\n",
    "            mem[(i, r)] = cur\n",
    "            return mem[(i, r)]\n",
    "        return dfs(finish, start, fuel)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        self.locations = locations\n",
    "        self.max_value = 10**9 + 7\n",
    "        return self.dfs(start, finish, fuel)\n",
    "        \n",
    "\n",
    "    @cache\n",
    "    def dfs(self, start: int, finish: int, fuel: int) -> int:\n",
    "        cnt = 1 if start == finish else 0\n",
    "        li = self.locations[start]\n",
    "        for i, lval in enumerate(self.locations):\n",
    "            if i!=start:\n",
    "                ifuel = fuel-abs(li-lval)\n",
    "                if ifuel>=0:\n",
    "                    cnt = cnt + self.dfs(i, finish, ifuel)\n",
    "                    if cnt>self.max_value: cnt -= self.max_value\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "        \n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        if abs(locations[start] - locations[finish]) > fuel:\n",
    "            # print(abs(locations[start] - locations[finish]))\n",
    "            return 0\n",
    "        \n",
    "        @cache\n",
    "        def dfs(cur: int, fuel: int) -> int:\n",
    "            if fuel < 0:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            if cur == finish:\n",
    "                if fuel == 0:\n",
    "                    return 1\n",
    "                ans = 1\n",
    "            for i, v in enumerate(locations):\n",
    "                if i == cur:\n",
    "                    continue\n",
    "                ans += dfs(i, fuel - abs(v - locations[cur]))\n",
    "            return ans % (10 ** 9 + 7)\n",
    "            \n",
    "        return dfs(start, fuel)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        if abs(locations[finish] - locations[start]) > fuel:\n",
    "            return 0\n",
    "        # dp[i, j]: 当剩余汽油量为i时, 从j城市出发到达终点的路径条数\n",
    "        n = len(locations)\n",
    "        dp = np.zeros(shape=(fuel + 1, n))\n",
    "        dp[0, finish] = 1\n",
    "\n",
    "        for i in range(1, fuel + 1):  # i: 剩余的油量\n",
    "            for j in range(n):  # j: 出发点\n",
    "                # 计算 dp[i, j]\n",
    "                subsum = 0\n",
    "                if j == finish:\n",
    "                    subsum = 1\n",
    "                for k in range(n):\n",
    "                    # 此时剩余的油量为: 当前油量减去两个地点间消耗的油量\n",
    "                    rest_fuel = i - abs(locations[j] - locations[k])\n",
    "                    if rest_fuel >= 0:\n",
    "                        subsum = (subsum + dp[rest_fuel, k]) % (10**9 +7)\n",
    "\n",
    "                dp[i, j] = subsum\n",
    "        return int(dp[fuel, start])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        if abs(locations[finish] - locations[start]) > fuel:\n",
    "            return 0\n",
    "        # dp[i, j]: 当剩余汽油量为i时, 从j城市出发到达终点的路径条数\n",
    "        n = len(locations)\n",
    "        dp = np.zeros(shape=(fuel + 1, n))\n",
    "        dp[0, finish] = 1\n",
    "\n",
    "        for i in range(1, fuel + 1):  # i: 剩余的油量\n",
    "            for j in range(n):  # j: 出发点\n",
    "                # 计算 dp[i, j]\n",
    "                subsum = 0\n",
    "                if j == finish:\n",
    "                    subsum = 1\n",
    "                for k in range(n):\n",
    "                    # 此时剩余的油量为: 当前油量减去两个地点间消耗的油量\n",
    "                    rest_fuel = i - abs(locations[j] - locations[k])\n",
    "                    if rest_fuel >= 0:\n",
    "                        subsum = (subsum + dp[rest_fuel, k]) % (10**9 +7)\n",
    "\n",
    "                dp[i, j] = subsum\n",
    "        return int(dp[fuel, start])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int,\n",
    "                    fuel: int) -> int:\n",
    "        if abs(locations[finish] - locations[start]) > fuel:\n",
    "            return 0\n",
    "        # dp[i, j]: 当剩余汽油量为i时, 从j城市出发到达终点的路径条数\n",
    "        n = len(locations)\n",
    "        dp = np.zeros(shape=(fuel + 1, n))\n",
    "        dp[0, finish] = 1\n",
    "\n",
    "        for i in range(1, fuel + 1):  # i: 剩余的油量\n",
    "            for j in range(n):  # j: 出发点\n",
    "                # 计算 dp[i, j]\n",
    "                subsum = 0\n",
    "                if j == finish:\n",
    "                    subsum = 1\n",
    "                for k in range(n):\n",
    "                    # 此时剩余的油量为: 当前油量减去两个地点间消耗的油量\n",
    "                    rest_fuel = i - abs(locations[j] - locations[k])\n",
    "                    if rest_fuel >= 0:\n",
    "                        subsum = (subsum + dp[rest_fuel, k]) % (10**9 +7)\n",
    "\n",
    "                dp[i, j] = subsum\n",
    "        print(dp)\n",
    "        return int(dp[fuel, start])\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        mod = int(1e9+7)\n",
    "        n = len(locations)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, tot):\n",
    "            # i表示当前所在的位置， tot表示当前的油量\n",
    "            if abs(locations[i]-locations[finish]) > fuel:\n",
    "                return 0\n",
    "            if tot < 0:\n",
    "                return 0\n",
    "\n",
    "            res = 0\n",
    "            for j in range(n):\n",
    "                if i == j: continue \n",
    "                t = abs(locations[j]-locations[i])\n",
    "                res += dfs(j, tot-t)\n",
    "\n",
    "            if i == finish:\n",
    "                res += 1\n",
    "\n",
    "            return res % mod \n",
    "    \n",
    "\n",
    "        return dfs(start, fuel)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur, fuel):\n",
    "            if fuel < 0:\n",
    "                return 0\n",
    "            ans = int(cur == finish)\n",
    "            for i, loc in enumerate(locations):\n",
    "                if i != cur:\n",
    "                    ans += dfs(i, fuel - abs(loc - locations[cur]))\n",
    "            return ans % MOD\n",
    "            \n",
    "        return dfs(start, fuel)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur, fuel):\n",
    "            if fuel < 0:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            if cur == finish:\n",
    "                ans = 1\n",
    "            for i, loc in enumerate(locations):\n",
    "                if i != cur:\n",
    "                    ans += dfs(i, fuel - abs(loc - locations[cur]))\n",
    "            return ans % MOD\n",
    "            \n",
    "        return dfs(start, fuel)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(curr_city, new_fuel):\n",
    "            if new_fuel < 0:\n",
    "                return 0\n",
    "            count = 0\n",
    "            if curr_city == finish:\n",
    "                count += 1\n",
    "            for i, num in enumerate(locations):\n",
    "                if i != curr_city:\n",
    "                    count += dfs(i, new_fuel - abs(locations[curr_city]-num))\n",
    "            return count\n",
    "        \n",
    "        # 如果一步到达不了，说明从位置 u 不能到达 end 位置\n",
    "        if fuel < abs(locations[finish]-locations[start]):\n",
    "            return 0\n",
    "        \n",
    "        count = 1 if start == finish else 0\n",
    "        for i, num in enumerate(locations):\n",
    "            if i != start:\n",
    "                count += dfs(i, fuel-abs(locations[start]-num))\n",
    "        return count % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def rec(i_loc, res_f):\n",
    "            ans = 0\n",
    "            if res_f < 0:\n",
    "                return 0\n",
    "            if i_loc == finish:\n",
    "                ans += 1\n",
    "            for i, _ in enumerate(locations):\n",
    "                if i != i_loc:\n",
    "                    ans += rec(i, res_f - abs(locations[i]-locations[i_loc]))\n",
    "            return ans\n",
    "        return rec(start, fuel)%(10**9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(idx, cost):\n",
    "            ans = 0\n",
    "            if cost > fuel: return ans\n",
    "            if idx == finish:\n",
    "                ans += 1\n",
    "            for i in range(len(locations)):\n",
    "                if idx != i:\n",
    "                    ans = (ans + dfs(i, cost + abs(locations[i] - locations[idx]))) % mod\n",
    "            return ans\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        return dfs(start, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i: int, k: int):\n",
    "            if k < 0:\n",
    "                return 0\n",
    "            ans = int(i == finish)\n",
    "            for j, x in enumerate(locations):\n",
    "                if j != i:\n",
    "                    ans = (ans + dfs(j, k - abs(locations[i] - x))) % mod\n",
    "            return ans\n",
    "\n",
    "        mod = 10**9 + 7\n",
    "        return dfs(start, fuel)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        @cache\n",
    "        def fn(p, f):\n",
    "            if f < 0:\n",
    "                return 0\n",
    "            res = 0\n",
    "            if p == finish:\n",
    "                res += 1\n",
    "\n",
    "            for i, l in enumerate(locations):\n",
    "                if i == p:\n",
    "                    continue\n",
    "                res += fn(i, f - (abs(locations[p] - l)))\n",
    "            return res % mod\n",
    "\n",
    "        return fn(start, fuel)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        cache_list = np.full((len(locations), fuel+1), -1)\n",
    "\n",
    "        def dfs(start_1, fuel_1):\n",
    "            if abs(locations[start_1] - locations[finish]) > fuel_1:\n",
    "                cache_list[start_1, fuel_1] = 0\n",
    "            else:\n",
    "                if cache_list[start_1, fuel_1] == -1:\n",
    "                    temp = 1 if (start_1 == finish) else 0\n",
    "                    for i in range(len(locations)):\n",
    "                        k = fuel_1 - abs(locations[i] - locations[start_1])\n",
    "                        if (i != start_1) & (k >= 0):\n",
    "                            temp += dfs(i, k)\n",
    "                    cache_list[start_1, fuel_1] = (temp % (10**9 + 7))\n",
    "            return cache_list[start_1, fuel_1]\n",
    "\n",
    "        dfs(start, fuel)\n",
    "        return int(cache_list[start, fuel])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10 ** 9 + 7\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        len_ = len(locations)\n",
    "        \n",
    "        # now: 当前处于城市位置\n",
    "        # cur: 当前剩余油量\n",
    "        @cache\n",
    "        def dfs(now, cur):\n",
    "            if cur == 0: return now == finish\n",
    "            if cur < 0 : return 0\n",
    "            sum_ = 1 if now == finish else 0\n",
    "            for i, n in enumerate(locations):\n",
    "                if i != now:\n",
    "                    sum_ += dfs(i, cur - abs(locations[now] - n))\n",
    "            return sum_ % mod\n",
    "        \n",
    "        return dfs(start, fuel)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        @cache\n",
    "        def dis(i, j):\n",
    "            return abs(locations[i] - locations[j])\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, f):\n",
    "            res = 0\n",
    "            if i == finish:\n",
    "                res += 1\n",
    "            for j in range(n):\n",
    "                if j != i and f >= dis(i, j):\n",
    "                    res += dfs(j, f - dis(i, j))\n",
    "            return res % (10 ** 9 + 7)\n",
    "\n",
    "        n = len(locations)\n",
    "        return dfs(start, fuel)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dis(i, j):\n",
    "            return abs(locations[i] - locations[j])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, f):\n",
    "            res = 0\n",
    "            if i == finish:\n",
    "                res += 1\n",
    "            for j in range(n):\n",
    "                if j != i and f >= dis(i, j):\n",
    "                    res += dfs(j, f - dis(i, j))\n",
    "            return res % (10 ** 9 + 7)\n",
    "\n",
    "        n = len(locations)\n",
    "        return dfs(start, fuel)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(x, f):\n",
    "            if f < 0:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for i in range(len(locations)):\n",
    "                if i != x:\n",
    "                    res += dfs(i, f - abs(locations[i] - locations[x]))\n",
    "            return res % (10 ** 9 + 7) if x != finish else (res + 1) % (10 ** 9 + 7)\n",
    "        return dfs(start, fuel)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(x, f):\n",
    "            if f < 0:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for i in range(len(locations)):\n",
    "                if i != x:\n",
    "                    res += dfs(i, f - abs(locations[i] - locations[x]))\n",
    "            return res % (10 ** 9 + 7) if x != finish else (res + 1) % (10 ** 9 + 7)\n",
    "        return dfs(start, fuel)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i, cnt):\n",
    "            ret = 0\n",
    "            if cnt > fuel:\n",
    "                return 0\n",
    "            elif i == finish:\n",
    "                ret = 1\n",
    "            for j in range(len(locations)):\n",
    "                if j == i: continue\n",
    "                ret += dfs(j, cnt + abs(locations[i] - locations[j]))\n",
    "            return ret % (10**9+7)\n",
    "        return dfs(start, 0) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        n = len(locations)\n",
    "        mod = 10 ** 9 + 7\n",
    "        @lru_cache(None)\n",
    "        def dfs(cur, left):\n",
    "            res = 0\n",
    "            if left < 0: return 0\n",
    "            if cur == finish: res += 1\n",
    "            for i in range(n):\n",
    "                if cur == i: continue\n",
    "                res += dfs(i, left - abs(locations[cur] - locations[i])) % mod\n",
    "            return res % mod\n",
    "        return dfs(start, fuel)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        cache_list = np.full((len(locations), fuel+1), -1)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(start_1, fuel_1):\n",
    "            if abs(locations[start_1] - locations[finish]) > fuel_1:\n",
    "                cache_list[start_1, fuel_1] = 0\n",
    "            else:\n",
    "                if cache_list[start_1, fuel_1] == -1:\n",
    "                    temp = 1 if (start_1 == finish) else 0\n",
    "                    for i in range(len(locations)):\n",
    "                        k = fuel_1 - abs(locations[i] - locations[start_1])\n",
    "                        if (i != start_1) & (k >= 0):\n",
    "                            temp += dfs(i, k)\n",
    "                    cache_list[start_1, fuel_1] = (temp % (10**9 + 7))\n",
    "            return cache_list[start_1, fuel_1]\n",
    "\n",
    "        dfs(start, fuel)\n",
    "        return int(cache_list[start, fuel])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        n=len(locations)\n",
    "        mod=10**9+7\n",
    "        @cache\n",
    "        def dfs(start,fuel):\n",
    "            if fuel==0:\n",
    "                return 1 if start==finish else 0\n",
    "            if fuel<0:\n",
    "                return 0\n",
    "            ans=0\n",
    "            if start==finish:\n",
    "                ans+=1\n",
    "            for j in range(n):\n",
    "                if j==start:\n",
    "                    continue\n",
    "                x=abs(locations[start]-locations[j])\n",
    "                ans+=dfs(j,fuel-x)\n",
    "            return ans\n",
    "        return dfs(start,fuel)%mod\n",
    "                            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countRoutes(self, locations: List[int], start: int, finish: int, fuel: int) -> int:\n",
    "        n = len(locations)\n",
    "        MOD = 10**9 + 7\n",
    "        def dis(x, y):\n",
    "            return abs(locations[x] - locations[y])\n",
    "        \n",
    "        @cache\n",
    "        def dfs(cur, remain) -> int:\n",
    "            if remain < 0:\n",
    "                return 0\n",
    "\n",
    "            res = 1 if cur == finish else 0\n",
    "\n",
    "            for nxt in range(n):\n",
    "                if nxt == cur:\n",
    "                    continue\n",
    "                r = dfs(nxt, remain - dis(nxt, cur))\n",
    "                res = (res + r) % MOD\n",
    "            return res\n",
    "        return dfs(start, fuel)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
